import functools


class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """

        @functools.cache
        def search(l, r):
            if l == r:
                return 1
            if r == l + 1:
                if s[l] == s[r]:
                    return 2
                else:
                    return 1
            if s[l] == s[r]:
                return search(l + 1, r - 1) + 2
            else:
                return max(search(l + 1, r), search(l, r - 1))

        return search(0, len(s) - 1)


data = Solution()
s = "bbbab"
print(data.longestPalindromeSubseq(s))
